package leetcode.top100;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
 * <p>
 * 说明：
 * <p>
 * 拆分时可以重复使用字典中的单词。
 * 你可以假设字典中没有重复的单词。
 * 示例 1：
 * <p>
 * 输入: s = "leetcode", wordDict = ["leet", "code"]
 * 输出: true
 * 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
 * 示例 2：
 * <p>
 * 输入: s = "applepenapple", wordDict = ["apple", "pen"]
 * 输出: true
 * 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
 *      注意你可以重复使用字典中的单词。
 * 示例 3：
 * <p>
 * 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
 * 输出: false
 * <p>
 * <p>
 * 动态规划见
 * {@link leetcode.a_总结分布.Code01_DP}
 *
 * @date 2020/4/14 23:24
 */
public class Code139_SplitWord_单词拆分 {
    public static void main(String[] args) {
        Code139_SplitWord_单词拆分 word = new Code139_SplitWord_单词拆分();
        String s = "leetcode";
        String s2 = "applepenapple";
        String s3 = "catsandog";
        List<String> list = new ArrayList<>();
        list.add("leet");
        list.add("code");
        list.add("apple");
        list.add("pen");
        String[] strs = {"cats", "dog", "sand", "and", "cat"};
        for (String str : strs) {
            list.add(str);
        }
        System.out.println(word.dp(s, list));
        System.out.println(word.dp(s2, list));
        System.out.println(word.dp(s3, list));
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0)
            return false;
        // return process(s, new HashSet<>(wordDict), 0);
        int[] memo = new int[s.length()];
        //memo[i]表示以第i个单词开头，第len-1个单词结束的子串是否在字典中
        //
        return process2(s, new HashSet<>(wordDict), 0, memo);
    }

    /**
     * 方式1：暴力递归
     *
     * @param s
     * @param wordDict
     * @param index
     * @return
     */
    private boolean process(String s, Set<String> wordDict, int index) {
        if (index >= s.length())
            return true;
        //对于s，从index一直到s.length去判断
        for (int i = index + 1; i <= s.length(); i++) {
            //如果包含index - i-1，继续递归s剩下的部分
            if (wordDict.contains(s.substring(index, i))) {
                //从s的i位置继续递归
                if (process(s, wordDict, i)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 方式2：记忆性回溯
     * 如 s = a b c..m..p 。在递归在以a为前缀的字符串时，递归到c时失败了，那么会进入以ab为前缀的递归。
     * 从ab开始递归时，又从c开始一直递归到p，这个过程的工作是重复的。
     * 开辟一个数组，作为有记忆。比如在上述过程中，将c的位置标记为false。
     * 所以进入ab的时候，在递归c为开头的，直接返回失败即可。
     */
    private boolean process2(String s, Set<String> wordDict, int index, int[] memo) {
        if (index >= s.length())
            return true;
        if (memo[index] != 0) return memo[index] == 1;
        //对于s，从index一直到s.length去判断
        for (int i = index + 1; i <= s.length(); i++) {
            //如果包含index - i-1，继续递归s剩下的部分
            if (wordDict.contains(s.substring(index, i))) {
                //从s的i位置继续递归
                if (process2(s, wordDict, i, memo)) {
                    memo[index] = 1;
                    return true;
                }
            }
        }
        memo[index] = -1;
        return false;
    }


    /**
     * 方式3：dp[i]表示s的前i个位置是否在字典中。
     * 如果知道dp[i-1],怎么判断dp[i]是否在字典中？
     * 1)直接判断0-i是否在字典中，若是，直接到i+1，否则转2)
     * 2)j从0到i-1开始找，dp[i] = dp[j] && list.contains(s.subString(j+1,i+1))
     */
    public boolean dp(String s, List<String> wordDict) {
        if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0)
            return false;
        boolean[] dp = new boolean[s.length()];
        Set<String> set = new HashSet<>(wordDict);
        dp[0] = set.contains(s.substring(0, 1));
        for (int i = 1; i < s.length(); i++) {
            //如果set直接含有0-i，直接为true
            if (set.contains(s.substring(0, i + 1))) {
                dp[i] = true;
                continue;
            }
            //dp[i] = dp[j] && list.contains(s.subString(j+1,i+1))
            for (int j = 0; j < i; j++) {
                if (dp[j] && set.contains(s.substring(j + 1, i + 1))) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.length() - 1];
    }
}
